МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
Національний університет “Львівська політехніка”
ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ К-ВНУТРIШНIХ ГРУПОВИХ СЕРЕДНІХ
Методичні вказівки
1.Мета роботи
Вивчити принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів.
Написати програму реалізації алгоритму з графічним інтерфейсом користувача.
2. Короткі теоретичні відомості
2.1. Алгоритм k-внутрішніх групових середніх розпізнавання образів
КРОК 1.
Вибираються к початкових центрiв кластерiв Z1(1), Z2(1),...,Zk(1).
Цей вибір здiйснюється довiльно i, звичайно, в якостi початкових центрiв використовуються першi k результатiв вибiрки з заданої множини образiв.
КРОК 2.
На k-му кроцi iтерацiї задана множина образiв розподiляється по k кластерах за таким правилом : XєSj(k), якщо ||X-Zj(k)||<=||X-Zj(k)||, для всiх i=1,2,...,k, i(j, де Sj(k) - множина образiв, якi входять в кластер з центром Zj(k). У випадку рiвностi рiшення приймаються довiльним чином.
КРОК 3.
На основi результатів кроку 2 визначаються новi центри кластерiв Zj(k+1), j=1,2,...,k, виходячи з умови, що сума квадратiв вiдстаней мiж усiма образами, що належать множині Sj(k), i новiм центром кластера повинна бути мiнiмальною. Iншими словами, новi центри кластерiв Zj(k+1) вибираються таким чином, щоб мiнiмiзувати показник якостi
Jj=(||X-Zj(k+1)||^2, j=1,2,...,k. XєSj(k)
Центр Zj(k+1), що забезпечує мiнiмiзацiю показника якостi, є, по сутi, вибiрковим середнiм, визначеним по множинi Sj(k). Вiдповiдно, новi центри кластерiв визначаються як:
Zj(k+1)=(1/Nj)(X, j=1,2,...,k, XЄSj(k),
де Nj- число вибiркових образiв, що входять в множину типу Sj(k).
Очевидно, що назва алгоритму "К внутрiшнiх групових" визначається способом, прийнятим для послiдовної корекцiї призначення центрiв кластерiв.
КРОК 4.
Рiвнiсть Zj(k+1) при j=1,2,...,k є умовою збiжностi алгоритму, i при її досягненнi виконання алгоритму припиняється. Iнакше, крок 2. Якiсть залежить:
вiд кiлькостi вибираємих центрiв кластерiв;
вiд вибору початкових центрiв кластерiв;
вiд послiдовностi проглядання образiв;
вiд геометричної особливостi даних.
Практичне застосування алгоритму вимагає проведення експериментiв, пов'язаних iз вибором рiзних значень параметра k i початковим розмiщенням центрiв кластерiв.
3. КОНТРОЛЬНІ ЗАПИТАННЯ
3.1. Поняття систем розпізнавання без навчання, таких, що навчають та самонавчальних.
3.2. Переваги та недоліки алгоритму k-внутрішніх групових середніх.
3.3. Схема алгоитму k-внутрішніх групових середніх.
3.4. Умова збіжності алгоритму k-внутрішніх групових середніх.
4. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Здійснити розпізнавання образів із застосуванням алгоритму k-внутрішніх групових середніх.
4.1. Х1(1,4), Х2(0,5), Х3(0,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7) , Х12(8,8) , Х13(10,8). K=3
4.2. Х1(4,5), Х2(6,6), Х3(7,7), Х4(8,8), Х5(7,15), Х6(8,15), Х7(9,15), Х8(10,15), Х9(11,15), Х10(14,2), Х11(15,3), Х12(17,5). K=5
4.3. Х1(0,1), Х2(0,3), Х3(0,4), Х4(4,1), Х5(5,1), Х6(5,2), Х7(5,3), Х8(6,9), Х9(8,6), Х10(9,2), Х11(9,5), Х12(9,6), Х13(9,7), Х14(10,2), Х15(10,3), Х16(10,4), Х17(11,3). K=4
4.4. Х1(1,1), Х2(2,0), Х3(5,1), Х4(2,1), Х5(3,1), Х6(2,2), Х7(7,5), Х8(7,6), Х9(19,6), Х10(19,7), Х11(18,9), Х12(19,8), Х13(21,8), Х14(10,9), Х15(11,9), Х16(9,10), Х17(10,10), Х18(10,11). K=5
4.5. Х1(1,1), Х2(1,0), Х3(0,2), Х4(2,4), Х5(2,9), Х6(2,9), Х7(3,8), Х8(4,4), Х9(3,10), Х10(7,6), Х11(7,8), Х12(9,9), Х13(8,7), Х14(8,9), Х15(10,3), Х16(11,3), Х17(11,2). K=3
4.6. Х1(0,3), Х2(0,5), Х3(0,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(10,10), Х13(20,8), Х14(20,9). K=4
4.7. Х1(5,5), Х2(6,6), Х3(7,7), Х4(8,8), Х5(7,15), Х6(8,15), Х7(9,15), Х8(10,15), Х9(11,15), Х10(14,2), Х11(15,3), Х12(17,4). K=4
4.8. Х1(0,9), Х2(3,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(9,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(10,12), Х12(20,8), Х13(20,9). K=3
4.9. Х1(0,3), Х2(2,0), Х3(1,1), Х4(2,1), Х5(3,1), Х6(2,2), Х7(7,...
